package arrAndstr;

import java.util.*;

/*
    133. 克隆图 --> 克隆一个无相连通图
 */
public class T133 {
    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    private static Map<Node, Node> map = new HashMap<>();
    public static Node cloneGraph(Node node) {
        // 如果节点数为0
        if (node == null)   return node;

        // 如果访问过 --> 说明克隆过，直接返回克隆的节点即可
        if (map.containsKey(node)) return map.get(node);

        Node newNode = new Node(node.val, new ArrayList<>());
        map.put(node, newNode); // 这步必须在递归临节点前
        for (Node neighbor : node.neighbors) {
            newNode.neighbors.add(cloneGraph(neighbor));
        }

        return newNode;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        List<Node> list1 = new ArrayList<>();
        list1.add(node2);
        list1.add(node4);
        List<Node> list2 = new ArrayList<>();
        list2.add(node1);
        list2.add(node3);
        List<Node> list3 = new ArrayList<>();
        list3.add(node2);
        list3.add(node4);
        List<Node> list4 = new ArrayList<>();
        list4.add(node1);
        list4.add(node3);
        node1.neighbors = list1;
        node2.neighbors = list2;
        node3.neighbors = list3;
        node4.neighbors = list4;

        Node node = cloneGraph(node1);
        Node newNode = cloneGraph(node);
        System.out.println(node==newNode);
    }

}
